#include <iostream>
#include<vector>
#include<stack>
using namespace std;
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
    vector<int> reversePrint(ListNode* head) {
        while(!m_stack.empty())
        {
            m_stack.pop();
        }
        for( ; head!=NULL; head = head->next)
        {
            m_stack.push(head->val);
        }
        vector<int> vec;
        while(!m_stack.empty())
        {
            vec.push_back(m_stack.top());
            m_stack.pop();
        }
        return vec;
    }
    ListNode * reverseList( ListNode* head)
    {
        ListNode* nextNode = NULL;
        ListNode* currentNode = NULL;
        while(head!=NULL)
        {
            nextNode = head->next;
            head->next = currentNode;
            currentNode = head;
            head = nextNode;
        }
        return currentNode;
    }
    ListNode * reverseList2( ListNode* head)
    {
        ListNode* nexthead = head->next;
        head->next = NULL;
        Solution slu;
        ListNode* tophead = NULL ;
//        ListNode* currenthead =NULL ;
        if(nexthead != NULL)
        {
            tophead = slu.reverseList2(nexthead);
            nexthead->next = head;
        }
        else tophead = head;
        return tophead;
    }
private:
    stack<int> m_stack;
};
int main() {
    ListNode head(5);
    ListNode second(6);
    ListNode third(7);
    head.next = &second;
    second.next = &third;
    Solution slu;
//    vector<int> aaaa = slu.reversePrint(&head);
//    ListNode* aaaa = slu.reverseList(&head);
    ListNode* aaaaa = slu.reverseList2(&head);

    vector<int> aa = slu.reversePrint(aaaaa);
    int i = 5;

}
